public class Test {
    public static void main(String[] args) {

    }
}

class Solution {
    public int triangleNumber(int[] nums) {
        //排序
        quicksort(nums,0,nums.length-1);
        int n=nums.length;
        int ret=0;
        for(int i=n-1;i>=2;i--){
            int left=0;
            int right=i-1;
            while(left<right){
                if(nums[left]+nums[right]>nums[i]){
                    ret+=right-left;
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return ret;
    }
    public void quicksort(int[]arr,int left,int right){
        if(left>=right){
            return;
        }
        int par=partiton(arr,left,right);
        quicksort(arr,left,par-1);
        quicksort(arr,par+1,right);
    }
    public int partiton(int[]arr,int start,int end){
        int pivot=arr[start];
        int i=start;
        while(start<end){
            while(start<end&&arr[end]>=pivot){
                end--;
            }
            while(start<end&&arr[start]<=pivot){
                start++;
            }
            swap(arr,start,end);
        }
        swap(arr,i,start);
        return start;
    }
    public void swap(int[]arr,int i,int j){
        int tem=arr[i];
        arr[i]=arr[j];
        arr[j]=tem;
    }


}
